package kata19;

import lombok.Data;

import java.util.*;
import java.util.stream.Collectors;

public class WordChains02 {

    private Set<String> chains;

    public WordChains02(Set<String> words) {
        chains = words;
    }

    /**
     * 1.获取近义词(一个字符相等的)
     * @param source
     * @return
     */
    public List<String> getSynonyms(String source){
        return chains.stream().filter(str -> {
            if(str.length() != source.length()){
                return false;
            }
            int charNotEqualsCount = 0;
            for(int i = 0;i < str.length(); i++){
                if(str.toCharArray()[i] != source.toCharArray()[i]){
                    ++charNotEqualsCount;
                }
            }
            return charNotEqualsCount == 1 ? true : false;
        }).collect(Collectors.toList());
    }

    /**
     * 2. 构造对象
     * @param source
     * @param target
     * @return
     */
    private MathWordNode buildingMathWordNode(String source,String target){
        MathWordNode parentNode = new MathWordNode(source);
        List<MathWordNode> children = getChildren(parentNode, target);
        if(children == null || children.size() == 0){
            return parentNode;
        }
        //递归构造
        buildingMathWordNode(parentNode,children,target);
        return parentNode;
    }

    /**
     * 2.1 递归构造
     * @param parentNode
     * @param children
     * @param target
     */
    private void buildingMathWordNode(MathWordNode parentNode,List<MathWordNode> children,String target){
        if(children == null || children.size() == 0){

        }
        parentNode.setMathNodes(children);
        for (MathWordNode node : children) {
            List<MathWordNode> inner = getChildren(node, target);
            buildingMathWordNode(node,inner,target);
        }
    }

    /**
     * 3. 获取 children 列表
     * @param parent
     * @param target
     * @return
     */
    private  List<MathWordNode>  getChildren(MathWordNode parent,String target){
        //获取近义词
        List<String> synonyms = getSynonyms(parent.getWord());
        //移除父节点已选中的近义词
        synonyms.removeAll(getSelectedWords(parent));
        //为空跳出
        if(synonyms == null || synonyms.size() == 0){
            return new ArrayList<>();
        }
        return synonyms.stream().map(word -> {
            //优先级
            int priority = 0;
            for (int i = 0; i < word.length(); i++) {
                for (int j = 0; j < target.length(); j++) {
                    if (word.toCharArray()[i] == target.toCharArray()[j]) {
                        ++priority;
                    }
                }
            }
            return new MathWordNode(word, priority, parent);
        }).collect(Collectors.toList());
    }

    private List<String> getSelectedWords(MathWordNode parent){
        MathWordNode cloneNode = new MathWordNode(parent.getWord(),parent.getPriority(),parent.getParent());
        cloneNode.setMathNodes(parent.getMathNodes());
        List<String> selectWords = new ArrayList<>();
        while (cloneNode.getParent() != null){
            selectWords.add(cloneNode.getWord());
            cloneNode = cloneNode.getParent();
        }
        return selectWords;
    }

    public List<String> getShortestChain(String source, String target) {
        MathWordNode wordNode = buildingMathWordNode(source, target);
        if(wordNode.getMathNodes() == null || wordNode.getMathNodes().size() == 0){
            return new ArrayList<>();
        }

        List<MathWordNode> nodes = new ArrayList<>();
        //查找
        getMathWordNode(wordNode, target, nodes);
        if(nodes == null || nodes.size() == 0){
            return new ArrayList<>();
        }

        //存在多个 , 则进行遍历查找 , 找出最短路径的一个
        Map<Integer,List<String>> map = new HashMap<>();
        for (MathWordNode mathWordNode : nodes) {
            //结果组合
            LinkedList<String> result = new LinkedList<>();
            while (mathWordNode.getParent() != null){
                result.addFirst(mathWordNode.getWord());
                mathWordNode = mathWordNode.getParent();
            }
            result.addFirst(source);
            map.put(result.size(),result);
        }

        Integer max = Collections.min(map.keySet());
        return map.get(max);
    }


    private void getMathWordNode(MathWordNode node, String target,List<MathWordNode> nodes) {
        //子节点为空，结束遍历
        if(node.getMathNodes() == null || node.getMathNodes().size() == 0){
            //排序,优先级高的先执行
           return;
        }
        List<MathWordNode> children = node.getMathNodes().stream().sorted(Comparator.comparing(MathWordNode::getPriority).reversed()).collect(Collectors.toList());
        node.setMathNodes(children);

        for (MathWordNode child : children) {
            if(child.getWord().equals(target)){
                //加入，结束当前递归
                nodes.add(child);
            }else {
                getMathWordNode(child,target,nodes);
            }
        }
    }


    @Data
    static class MathWordNode {
        //父节点
        private MathWordNode parent;

        //源单词
        private String word;

        //优先级别
        private int priority;

        //相似单词，不能是同级别
        private List<MathWordNode> mathNodes;

        public MathWordNode(String word){
            this(word,0,null);
        }

        public MathWordNode(String word,int priority,MathWordNode parent){
            this.word = word;
            this.priority = priority;
            this.parent = parent;
        }

        @Override
        public String toString() {
            return "MathWordNode{" +
                    "parent=" + parent +
                    ", word='" + word + '\'' +
                    ", priority=" + priority +
                    ", mathNodes=" + mathNodes +
                    '}';
        }
    }



}
